import java.util.*;

class Solution2 {

    public int reversePairs(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] temp = new int[nums.length];
        return sort(nums, 0, nums.length - 1, temp);
    }

    private int sort(int[] arr, int left, int right, int[] temp) {
        int count = 0;
        if (left < right) {
            int mid = (left + right) >> 1;
            count += sort(arr, left, mid, temp);
            count += sort(arr, mid + 1, right, temp);
            int i = mid, j = right, k = right;
            while (i >= left && j >= mid + 1) {
                if (arr[i] > arr[j]) {
                    count += (j - mid);
                    temp[k--] = arr[i--];
                } else {
                    temp[k--] = arr[j--];
                }
            }
            while (i >= left) {
                temp[k--] = arr[i--];
            }
            while (j >= mid + 1) {
                temp[k--] = arr[j--];
            }
            k = left; // 注意这里不能从0开始
            for (int l = left; l <= right; l++) {
                arr[l] = temp[k++];
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 6, 7, 3, 4, 9, 2, 2, 3, 1};
        Solution s = new Solution();
        System.out.println(s.reversePairs(nums));
        System.out.println(Arrays.toString(nums));
    }
}